/**
 * 三个数字加起来和目标值是一样的
 * 方法一: 使用三层循环, 但是这样是不好的!
 * 方法二:
 */
// 方法一: 最蠢的方法， 就是全排列， 这样会有重复
const arr = [1, 1, 2, 3, 4, 5, 6, 6, 7, 8, 8]
function T1(arr, target) {
    let res= []
    for(let i=0; i<arr.length-1; i++) {
        for(let j = 0; j<arr.length-1; j++){
            if(arr[i] === arr[j]) continue;
            for(let z= 0; z<arr.length -1; z++) {
                if(arr[i] === arr[j] === arr[z]) continue
                if(arr[i] + arr[j] + arr[z] === target) res.push([i,j,z])
            }
        }
    }
    return res;
}

// 这和三层for循环其实是一样的.
function T2(arr, target) {
    if(!arr.length || target === undefined) return []
    // 定义一个空数组返回答案
    const res = []
    // 先循环， i， 然后i后面用两个指针， 根据条件前后移动即可
    for (let i = 0; i < arr.length - 1; i++) {
        // 左指针比当前i大一个， 右指针是数组最后一个
        let left = i + 1, right = arr.length - 1
        // 如果起步就大于target，直接跳过， 或者直接返回一个空数组
        if(arr[i] >= target) continue;

        // 左右指针反复横跳
        while (left < right) {
            // 如果当前的满足条件， push进去
            if (arr[left] + arr[right] + arr[i] === target) {
                res.push([arr[i], arr[left], arr[right]])
                // 去重
                while (left < right && arr[left] === arr[left + 1]) left++
                while (left < right && arr[right] === arr[right - 1]) right--
                // 左右向中间移动
                left++;
                right--
            } else if (arr[left] + arr[right] + arr[i] < target) {
                // 小了， 往大的移
                left++
            } else {
                // 大了，往小的移
                right--
            }
        }
    }
    return res;
}

console.log(T2(arr, 10));

/**
 *
 * @constructor
 */
// TODO：复习
function T3(arr, target) {
    if(!arr.length || target === undefined) return null
    let res = []

    for(let i= 0; i<arr.length -1; i++) {
        let left= i + 1, right = arr.length - 1
        while(left < right) {
            if(arr[left] + arr[right] + arr[i] === target) {
                res.push([arr[i], arr[left], arr[right]])
                while(left < right && arr[left] === arr[left +1 ]) left++
                while(left < right && arr[right] === arr[right -1]) right--
                left++;
                right--
            }else if(arr[left] + arr[right] + arr[i] < target) {
                left++
            }else {
                right--
            }
        }
    }
    return res;
}


function ThreeSum(arr, target) {
    let res = [], len = arr.length
    for (let i = 0; i < len; i++) {
        let left = i + 1, right = len
        while (left < right) {
            if (arr[i] + arr[left] + arr[right] === target) {
                res.push([arr[i], arr[left], arr[right]])
                while (left < right && arr[left] === arr[left + 1]) left++
                while (left < right && arr[right] === arr[right - 1]) right--
                left++
                right--
            } else if (arr[i] + arr[left] + arr[right] < target) {
                left++
            } else {
                right--
            }

        }
    }
    return res;
}


function T(nums, target) {
    const len = nums.length, res = []
    for (let i = 0; i < len; i++) {
        let left = i+1, right = len;
        while(left < right){
            if(nums[left] + nums[right] + nums[i] === target) {
                res.push([nums[i], nums[left], nums[right]])

                while(left < right && nums[left] === nums[left+1]) left++
                while(left < right && nums[right] === nums[right-1]) right--
                left++
                right--
            }else if(nums[i]+nums[left]+nums[right] < target) {
                left++
            }else{
                right--
            }
        }
    }
    return res;
}
